package com.lzq.leetcode.hoot100;

import java.util.HashMap;
import java.util.Map;

public class s76 {

    public String minWindow(String s, String t) {

        int lenS = s.length();
        int lenT = t.length();
        int l = 0, r = 0;

        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i=0; i<lenT; i++) {
            char c = t.charAt(i);
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        boolean isOk = false;
        int minL = -1, minR = lenS;
        while (r < lenS) {
            char cs = s.charAt(r++);
            if (!tMap.containsKey(cs)) {
                continue;
            }
            sMap.put(cs, sMap.getOrDefault(cs, 0) + 1);
            // 比较
            while (ok(sMap, tMap)) {
                if (r - l < minR - minL) {
                    minR = r;
                    minL = l;
                }
                if (sMap.containsKey(s.charAt(l))) {
                    sMap.put(s.charAt(l), sMap.get(s.charAt(l)) - 1);
                }
                ++l;
            }
        }
        return minL == -1 ? "" : s.substring(minL, minR);
    }

    private boolean ok(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
        boolean flag = true;
        for (Character c : tMap.keySet()) {
            if ((!sMap.containsKey(c)) || sMap.get(c) < tMap.get(c)) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        System.out.println(new s76().minWindow("aa", "a"));
    }
}
